package com.ljx.QueueStack;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author 李加喜
 * @Package com.ljx.QueueStack
 * @date 2021-12-09 9:54
 */
// 496  下一个更大的元素 使用的是单调递增栈
public class NextMaxNum {
    public static void main(String[] args) {
        NextMaxNum nextMaxNum = new NextMaxNum();
//        int[] num1={4,1,2};
//        int[] num2={1,3,4,2};
        int[] num1={6,6};
        int[] num2={1,2,3,4,5,6,7,8};
        System.out.println(Arrays.toString(nextMaxNum.nextGreaterElement(num1, num2)));
    }
    // nums1是num2的子集
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int length1=nums1.length;
        int length2=nums2.length;
        // 记录那些比自己打的值
        int[] res=new int[length2+1];
        int[] success=new int[length1];
        Stack<Integer> stack = new Stack<>();
        for(int i=length2-1;i>=0;i--){
            while (!stack.isEmpty()&&stack.peek()<=nums2[i]){
                // 比当前值小 不需要
                // 因为他们的存在没有意义，前⾯挡着个
                //「更⾼」的元素，所以他们不可能被作为后续进来的元素的 Next Great Number 了  核心部分
                stack.pop();
            }
            res[i]=stack.isEmpty()?-1:stack.peek();
            stack.push(nums2[i]);
        }
        // map主要用来记录元素的下标的
        Map<Integer, Integer> map = new HashMap<>(16);
        for (int i=0;i<length2;i++){
            map.put(nums2[i],i);
        }
        for (int i=0;i<length1;i++){
            success[i]=res[map.get(nums1[i])];
        }
        return success;
    }
//    vector<int> nextGreaterElement(vector<int>& nums) {
//        vector<int> res(nums.size()); // 存放答案的数组
//        stack<int> s;
//// 倒着往栈⾥放
//        for (int i = nums.size() - 1; i >= 0; i--) {
//// 判定个⼦⾼矮
//            while (!s.empty() && s.top() <= nums[i]) {
//// 矮个起开，反正也被挡着了。。。
//                s.pop();
//            }
//// nums[i] 身后的 next great number
//            res[i] = s.empty() ? -1 : s.top();
                // 这里压栈之后  在进行出栈是顺序的  所以获取的数字就会是第一个值
//            s.push(nums[i]);
//        }
//        return res;
//    }
}
